import java.util.Random;

/*
partition过程：

  4   1   2   5   3
start            end

3作为中间值
------------------------------
for循环执行完：

   1    2    4    5    3
  start    small      end
------------------------------
交换small和end位置元素后：
1 2   3   4 5
    small
返回中间值位置的索引：2
 */
public class QuickSort<T extends Comparable<T>> {

    public void quickSort(T[] data) {
        quickSort(data, 0, data.length - 1);
    }

    private void quickSort(T[] data, int start, int end) {
        if (start >= end)
            return;

        int mid = partition(data, start, end);
        quickSort(data, start, mid - 1);
        quickSort(data, mid+1, end);
    }

    // partition data数组的[start, end]区间的元素
    private int partition(T[] data, int start, int end) {
        Random r = new Random(System.currentTimeMillis());
        //返回[start, end]区间的任意元素
        int midIndex = r.nextInt(end - start + 1) + start;//假定这个索引为中间值，进行partition

        //把中间值放到data[end]位置
        T tem = data[midIndex];
        data[midIndex] = data[end];
        data[end] = tem;

        int small = start;//small索引左边的元素都是小于中间值的
        for (int i = start; i < end; i++) {
            if (data[end].compareTo(data[i]) > 0) {
                T temp = data[i];
                data[i] = data[small];
                data[small] = temp;
                small++;
            }
        }
        //把中间值放到 中间位置
        tem = data[end];
        data[end] = data[small];
        data[small] = tem;

        return small;//返回中间值的索引
    }

    public static void main(String[] args) {

        Integer[] arr = {2, 1, 4, 7, 5, 3, 8, 9, 4, 1, 0};
        new QuickSort<Integer>().quickSort(arr);
        System.out.println();
    }

}
